package com.xuzz.study.datastructure;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhize.xu
 * @version 1.0
 * @ClassName:MyHashMap
 * @Description:
 * @date 2018/11/20 14:48
 */
public class MyHashMap<K,V> implements Map<K,V> {
    private static final int DEFAULT_CAPA_SIZE=1<<4;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int capaSize;
    private float loadFactor;

    private int usedSize;

    private Entry<K,V>[] table = null;

    public MyHashMap()
    {
        this(DEFAULT_CAPA_SIZE,DEFAULT_LOAD_FACTOR);
    }
    public MyHashMap(int initCapaSize,float initLoadFactor)
    {
        if(initCapaSize<=0)
        {
            throw new IllegalArgumentException("capacity error");
        }
        if(initLoadFactor<=0)
        {
            throw  new IllegalArgumentException("load factory error");
        }

        this.capaSize = initCapaSize;
        this.loadFactor = initLoadFactor;

        table = new Entry[this.capaSize];
    }

    class Entry<K,V> implements Map.Entry<K,V>
    {
        K key;
        V value;
        Entry<K,V> next;

        public Entry(){}
        public Entry(K k,V v,Entry<K,V> next)
        {
            this.key = k;
            this.value=v;
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

    public V put(K k, V v) {
        V oldValue = null;
        //判断是否需要扩容
        if(usedSize>=(loadFactor*capaSize))
        {
            resize(2*capaSize);
        }

        //根据hash值得到位置

           //等价于hash(k)%capaSize
           //hash(k)%capaSize == hash(k)&(capaSize-1)
        int index = hash(k) & (capaSize-1);

        if(null==table[index])
        {
            table[index]=new Entry<>(k,v,null);
            ++usedSize;
        }
        else
        {
            Entry<K,V> entry = table[index];
            Entry<K,V> e = entry;
            while(null!=e)
            {
                //如果是同一个key，则替换
                if(k==e.getKey() || e.equals(e.getKey()))
                {
                    oldValue = e.value;
                    e.value=v;
                    return oldValue;
                }
                e = e.next;
            }
            //如果循环完链表后还没有找到相同key的，则插入新数据
            table[index] = new Entry<>(k,v,entry);
            ++usedSize;
        }

        return oldValue;
    }

    public V get(K k) {

        //计算位置
        int index = hash(k) & (capaSize-1);

        Entry<K,V> entry = table[index];
        while(null!=entry)
        {
            if(k ==entry.getKey() || k.equals(entry.getKey()))
            {
                return entry.value;
            }
            entry = entry.next;
        }

        return null;
    }

    private void resize(int newCapaSize)
    {
        Entry[] newTable = new Entry[newCapaSize];
        usedSize = 0 ;
        capaSize = newCapaSize;

        rehash(newTable);
    }

    /**
     * 扩容后重新计算hash
     * @param newTable
     */
    private void rehash(Entry[] newTable)
    {
        //将原来所有的entry，先暂存到一个集合中
        List<Entry<K,V>> oldEntrys = new ArrayList<>();
        for(Entry<K,V> entry:table)
        {
            if(null!=entry)
            {
                do {
                    oldEntrys.add(entry);
                    entry = entry.next;
                }while(null!=entry);
            }
        }

        if(newTable.length>0)
        {
            table = newTable;
        }

        for(Entry<K,V> entry:oldEntrys)
        {
            put(entry.getKey(),entry.getValue());
        }
    }

    private int hash(K key)
    {
        int h;
        //key的hash值高16位不变，低16位与高16位异或
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

}
